A content-addressable memory (CAM), also known as an associative memory, is a hardware implementation of associative processing. Associative processing manipulates data based on matching, or associating, an input value with other values stored in an array. Associative-processing hardware incorporates a limited amount of computational capability at each memory location that allows the entire memory array to be examined at once. CAMs combine these functions with a control structure to perform associative processing. A CAM compares an input value, the comparand, to all the associative data stored in the memory array at once. The output from a CAM can be a flag that indicates one or more matches and/or associated data that is related in some way to the matched values.
A CAM makes it possible to handle list searches and data translation as embedded functions within a system. The combination of a CAM and a state machine creates an economical controller for real-time processes that need to perform look-ups, data translations, and entry maintenance in sparsely populated tables--ones with few entries compared to the address space required for direct table look-up. For example, an asynchronous transfer mode (ATM) switch must search internal tables that hold the necessary information for each connection that routes through the switch. The index to these tables is the virtual-path identifier (VPI) for the VPI/virtual channel identifier (VCI) combination from the header of an incoming data cell. The switch uses this information to look up the VPI and VCI for the outgoing link, the internal path through the switch to the correct output port, billing rates, traffic-flow parameters, flags for any special functions, etc. A CAM is particularly suited for such an application.
A CAM is implemented as a circuit--often as an integrated-circuit device--and as such it adds to the cost of a system which employs the CAM. At the same time, the system may employ one of many commercially-available microprocessors and microcontrollers that include internal cache memories and control, as well as internal memory management units (MMUs), that use associative processing for cache line control and memory-management address-translation. And in many embedded applications, the MMU is not used.
One alternative to the use of a CAM is to use software-based linear and binary table searches. Since these searches are implemented in software, they dispense with the need for a dedicated circuit to perform these functions. But such searches require extensive shuffling of the data list to add or delete data entries. To add an item of data to a sorted data list, every entry from the end of the data table to the location of the new entry must be read and then written into the next location. Removal of an entry requires the same process in reverse. Search times depend on the size of the data list.